import { BinTree } from './BinTree'

const bt: BinTree = {
  val: 1,
  left: {
    val: 2,
    left: {
      val: 4,
      left: null,
      right: null,
    },
    right: {
      val: 5,
      left: null,
      right: null,
    },
  },
  right: {
    val: 3,
    left: {
      val: 6,
      left: null,
      right: null,
    },
    right: {
      val: 7,
      left: null,
      right: null,
    },
  },
}

/**
 * 中序遍历二叉树
 * @param root 根节点
 * @returns 
 */
/* const inorder = (root: BinTree | null) => {
  if (!root) {
    return
  }
  inorder(root.left)
  console.log(root.val)
  inorder(root.right)
} */

const inorder = (root: BinTree | null) => {
  if (!root) {
    return
  }
  const stack: BinTree[] = []
  let p: BinTree | null | undefined = root
  while (stack.length || p) {
    // 先一直把左子树压进去，再压右子树
    while (p) {
      stack.push(p)
      p = p.left
    }
    // 出栈
    const n = stack.pop()
    // 打印值
    console.log(n?.val)
    p = n?.right
  }
}

inorder(bt)

